/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2024-04-08
 * Time: 11:01
 */
//53.最大子数组和
class Solution1 {
    public int maxSubArray(int[] nums) {
        //1.状态表示 dp[i]表示以i结尾的所有子数组的最大值
        int n = nums.length;
        int[] dp = new int[n+1];
        //2.初始化
        dp[0] = 0;
        //3.状态转移方程
        int ret = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++) {
            dp[i] = Math.max(dp[i-1]+nums[i-1],nums[i-1]);
            ret = Math.max(ret,dp[i]);
        }
        //4.填表顺序
        //5.返回值 dp表最大值
        return ret;
    }
}
